|
In theoretical computer science and formal language theory, a prefix grammar is a type of string rewriting system, consisting of a set of string rewriting rules, and similar to a formal grammar or a semi-Thue system. What is specific about prefix grammars is not the shape of their rules, but the way in which they are applied: only prefixes are rewritten. The prefix grammars describe exactly all regular languages.〔(M. Frazier and C. D. Page. Prefix grammars: An alternative characterization of the regular languages. Information Processing Letters, 51(2):67–71, 1994. )〕 ==Formal definition== A prefix grammar ''G'' is a 3-tuple, (Σ, ''S'', ''P''), where *Σ is a finite alphabet *''S'' is a finite set of base strings over Σ *''P'' is a set of production rules of the form ''u'' → ''v'' where ''u'' and ''v'' are strings over Σ For strings ''x'', ''y'', we write ''x →G y'' (and say: ''G'' can derive ''y'' from ''x'' in one step) if there are strings ''u, v, w'' such that ''x = vu, y = wu'', and ''v → w'' is in ''P''. Note that ''→G'' is a binary relation on the strings of Σ. The ''language'' of ''G'', denoted ''L(G)'', is the set of strings derivable from ''S'' in zero or more steps: formally, the set of strings ''w'' such that for some ''s'' in ''S'', ''s R w'', where ''R'' is the transitive closure of ''→G''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Prefix grammar」の詳細全文を読む スポンサード リンク
|